Abstract:
The Multiway-Cut problem is a fundamental graph partitioning problem in which the objective is to find a minimum weight set of edges disconnecting a given set of special vertices called terminals. This problem is NP-hard and there is a well-known geometric relaxation in which the graph is embedded into a high dimensional simplex.
Rounding a solution to the geometric relaxation is equivalent to partitioning the simplex. We present a new simplex partitioning algorithm which is based on competing exponential clocks and distortion.
Unlike previous methods, it utilizes cuts that are not parallel to the faces of the simplex. Applying this partitioning algorithm to the Multiway-Cut problem, we obtain a simple $(4/3)$-approximation algorithm, thus, improving upon the current best known result. This bound is further pushed to obtain an approximation factor of $1.32388$.
It is known that under the assumption of the unique games conjecture, the best possible approximation for the MultiWay-Cut problem can be attained via the geometric relaxation.
We will also mention some very recent developments relating to the new simplex partitioning algorithm.

Joint work with Niv Buchbinder and Joseph (Seffi) Naor.